package hot100;

//
//输入：s = "abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"

//
//
// 示例 2：
//
//
//输入：s = "aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
//
//


/**
 * abc
 * a
 * b
 * c
 * ab
 * ac
 * bc
 * abc
 *
 */
public class Solution647 {

    public int countSubstrings1(String s) {
        int num = 0;
        for (int i = 0; i < 2 * (s.length() - 1); i++) {
            int left = i / 2;
            int right = (i % 2 == 0) ? left : left + 1;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
                num++;
            }
        }
        return num;
    }

    public int countSubstrings(String s) {
        int num = 0;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            stringBuilder.append("#").append(s.charAt(i));
        }
        s = stringBuilder.append("#").toString();
        int[] f = new int[s.length()];
        // 回文字符串最右端
        int right = -1;
        // 回文中心
        int j = -1;
        for (int i = 0; i < s.length(); i++) {
            if (right >= i) {
                int k = j - (i - j);
                int minLen = Math.min(f[k], right - i);
                f[i] = expand(s, i - minLen, i + minLen);
            } else {
                f[i] = expand(s, i, i);
            }
            if (i + f[i] > right) {
                right = i + f[i];
                j = i;
            }
            num += f[i] / 2;
        }
        return num;
    }
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return (right - left) / 2;
    }

    public static void main(String[] args) {
        Solution647 solution647 = new Solution647();
        System.out.println(solution647.countSubstrings("bab"));
    }
}
